The digital halftone technique in the field of image processing can convert a continuous tone image to a binary tone image. Recently, an Error Diffusion method based on the digital halftone technique is used widely. According to the Error Diffusion method, when a gray value of each pixel in an original image is compared with a threshold to generate a dot, an error between the gray value of the pixel and the threshold is diffused to pixels adjacent to the pixel. For example, in an image with 256 gray levels, the threshold is set as 127. After comparing, a pixel whose gray value is 150 will be converted to a white dot (the gray value of a white dot is 255). However, this dot should not be purely white. A difference between the gray values of the dot and a white dot is equal to 105. In this case, the error value 105 is diffused to adjacent dots around the dot by a certain means.
In many algorithms for diffusing errors to adjacent pixels, Floyd-Steinberg Algorithm is a common algorithm for Error Diffusion method. By using the Floyd-Steinberg Algorithm, the error of a pixel is diffused to four adjacent pixels. According to the Floyd-Steinberg Algorithm, after the gray value of the current pixel is compared with a threshold, the gray value of the pixel is set as 1 or 0 (i.e. the corresponding dot is set as a black or white dot). Then, the error is obtained by calculation and distributed to adjacent pixels to adjust the gray values of the adjacent pixels. FIG. 1A is a diagram illustrating error diffusion and distribution based on the Floyd-Steinberg Algorithm. Based on the Floyd-Steinberg Algorithm, the error of a current pixel * is distributed to four pixels adjacent to the current pixel according to the ratios shown in FIG. 1A. Specifically, 7/16 of the error value is added to a pixel adjacent to and on the right side of the current pixel, 5/16 of the error value is added to a pixel in the next row, which corresponds to the current pixel, 3/16 of the error value is added to a pixel, which is adjacent to and on the left side of the pixel in the next row corresponding to the current pixel, and 1/16 of the error value is added to a pixel, which is adjacent to and on the right side of the pixel in the next row corresponding to the current pixel. This process is implemented to each pixel in the image for halftoning and revising the gray values.
Theoretically, the gradations and the colors of the original image can be reflected well by using the Error Diffusion method. More pixels involved in the error diffusion of a pixel will result in a better effect. Some improved algorithms such as Stucki Algorithm have arisen on the basis of the Floyd-Steinberg Algorithm. FIG. 2 illustrates error diffusion and distribution based on the Stucki Algorithm. Based on the Stucki Algorithm, the error of a current pixel * is distributed to twelve pixels adjacent to the current pixel, as shown in FIG. 2. In general, some of these twelve positions have the same error distribution ratio. It only needs five different error distribution ratios, wherein D1=1/44, D2=2/44, D3=5/44, D4=4/44, and D5=8/44. The output image has a better effect because more pixels are related to according to the Stucki Algorithm.
In the processing of an image, more pixels involved in the error diffusion of a pixel will result in more calculation and slower processing speed. In the devices for generating frequency modulation dots in a high speed using a hardware circuit, the speed of reading and writing the memory impacts speed of generating the frequency modulation dots significantly. According to the conventional Error Diffusion method, large numbers of read-write operations on the memory arise, which restricts the use of the Error Diffusion method.
Although many researches have been practiced for improving the speed of generating frequency modulation dots, it still need implement at least one read operation and at least one write operation on the memory for one pixel during the error diffusion and the read operation and the write operation are implemented separately, which impacts the speed of generating dots significantly.